#include <iostream>
#include <vector>
#include "main/utils.h"
using namespace std;

int patition(vector<int> vec, int begin, int end) {
  int index = begin;
  while (begin <= end) {
    while (vec[begin] <= vec[index]) {
      ++begin;
    }
    while (vec[end] > vec[index]) {
      --end;
    }
    if (begin < end)
      swap(vec, begin, end);
  }
  swap(vec, index, end);
  return index;
}

int moreThanHalfNum(vector<int> vec) {
  int length = vec.size();
  int begin = 0;
  int end = length - 1;
  int index = patition(vec, begin, end);
  int mid = length / 2;
  while (index != mid) {
    if (index < mid) {
      begin = index + 1;
    } else {
      end = index - 1;
    }
    index = patition(vec, begin, end);
  }
  // check number is more than half of vector
  return vec[index];
}

int moreThanHalfNum2(vector<int> vec) {
  if (vec.empty())
    return -1;
  int length = vec.size();
  int ret = vec[0];
  int times = 1;
  for (int i = 1; i < length; ++i) {
    if (vec[i] == ret) {
      ++times;
    } else {
      if (times == 0) {
        times = 1;
        ret = vec[i];
      } else {
        --times;
      }
    }
  }
  return ret;
}

int main() {
  vector<int> vec = {2, 2, 1, 2, 3, 2, 2, 2, 5, 4, 2, 3, 4};
  int ret = moreThanHalfNum(vec);
  cout << "MoreThanHalfNum by partition: " << ret << endl;
  
  ret = moreThanHalfNum2(vec);
  cout << "MoreThanHalfNum2: " << ret << endl;
}
